In general, machine learning operates by processing a set of examples to develop a learned mechanism, such that when given new data the learned mechanism can correctly estimate a result. For example, machine learning may be used to train a classifier with samples, such that in later use, the classifier correctly classifies unknown input, e.g., a handwritten character.
One problem that occurs in machine learning is overfitting, in which the mechanism being learned fits the particular set of examples too closely. When enough of the examples are bad examples (e.g., noisy or associated with other errors such as mislabeled), the learned mechanism learns relatively too much from the bad examples and is thus not as accurate when later processing new data. Regularization generally refers to preventing such overfitting.
Online learning algorithms are those that process samples sequentially as each becomes available, in contrast to having to process significant other data (e.g., a whole set of samples together). In general, online algorithms operate by repetitively drawing random examples, one at a time, and adjusting learning variables using calculations that are usually based on the single example only. Because of the sequential, one-at-a-time approach, online algorithms are often used to solve large-scale learning problems.
Traditional online algorithms, such as stochastic gradient descent, have limited capability for solving regularized learning problems. What is needed are methods for stochastic and/or online learning that obtain desired regularization effects, e.g., desired sparsity in the training parameters.